package leetcode.code0886;

public class Solution {

	public boolean possibleBipartition(int n, int[][] dislikes) {
		UnionFind union = new UnionFind(n + 1);
		int[] dis = new int[n + 1];
		for (int i = 0; i < dislikes.length; i++) {
			int d[] = dislikes[i];
			int a = d[0], b = d[1];
			if (union.isSameSet(a, b)) {
				return false;
			}
			if (dis[a] == 0) {
				dis[a] = b;
			} else {
				union.union(dis[a], b);
			}
			if (dis[b] == 0) {
				dis[b] = a;
			} else {
				union.union(dis[b], a);
			}
		}
		return true;
	}

	class UnionFind {
		int[] roots;
		int[] sizes;
		int[] stack;

		public UnionFind(int n) {
			roots = new int[n];
			sizes = new int[n];
			for (int i = 0; i < n; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[n];
		}

		public int findRoot(int id) {
			int root = 0;
			int p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
				}
			}
		}
	}

}
